\chapter{Compiler}
\label{chap-compiler}

\section{General description}

The \sysname{} compiler turns source code into executable machine
code.  The source code can be either a \emph{file} or an
\emph{s-expression} depending on how the compiler is used, as
described in \refSec{sec-different-uses-of-the-compiler}.

User-supplied code is relatively simple in that the end result
consists of literals, references and calls to functions, and
references and assignments of variable.

However, the compiler is also used to compiler system-specific code.
For example, the \texttt{car} function must refer to en even
lower-level primitive that takes the \texttt{car} of an object known
to be a \texttt{cons} cell.  Similarly the function
\texttt{standard-instance-access} must refer to an even lower-level
primitive that accesses the slots of a standard object.  The compiler
must be able to compile these functions as well, in addition to
user-level code.  For that reason, \sysname{} defines a set of
\emph{primitive operations} or \emph{primitives} for short.  In code
such as the definition of \texttt{car} the primitive is invoked as if
it were a function, with the semantics of a function call, but it is
not defined as a function.  In High-level Intermediate Representation
(or HIR, \refSec{sec-conversion-from-ast-to-hir}) these primitives
look like calls to global functions.  The only \sysname{}-specific
aspect of the compiler is the conversion of High-level Intermediate
Representation to Medium-level Intermediate Representation, because
this is the phase where these primitives are turned into code that
exposes the representation of objects and that representation is
\sysname{} specific.

Primitives are defined with names in a separate package called
\texttt{sicl-primitives}, and they can be divided into groups
according to the kind of objects they operate on:

\begin{itemize}
\item \texttt{cons} cells.
\item standard objects.
\item arrays.
\item numbers.
\end{itemize}

The following primitives are defined for \texttt{cons} cells:

\begin{itemize}
\item \texttt{car}.  Return the object in the \texttt{car} slot of an
  object known to be a \texttt{cons} cell.
\item \texttt{rplaca}.  Store an arbitrary object in the \texttt{car}
  slot of an object known to be a \texttt{cons} cell.
\item \texttt{cdr}.  Return the object in the \texttt{cdr} slot of an
  object known to be a \texttt{cons} cell.
\item \texttt{rplacd}.  Store an arbitrary object in the \texttt{cdr}
  slot of an object known to be a \texttt{cons} cell.
\end{itemize}

The following primitives are defined for standard objects:

\begin{itemize}
\item \texttt{standard-instance-access}.  Return the contents of a
  slot at a particular index of an object known to be a standard
  object.
\item \texttt{(setf standard-instance-access)}.  Store an arbitrary
  object in a slot at a particular index of an object known to be a
  standard object.
\end{itemize}

For arrays, there is a pair of primitives for each specialized type of
array, as required by the \regalia{} library described in \refSec{sec-array}:

\begin{itemize}
\item \texttt{t-aref}.  Return an element at a given index of an
  unspecialized array.
\item \texttt{(setf t-aref)}.  Store an object in the element at a
  given index of an unspecialized array.
\item \texttt{signed-64-bit-aref}.  Return an element at a given index
  of an array of signed 64-bit integers.
\item \texttt{(setf signed-64-bit-aref)}.  Store an object in the
  element at a given index of
\item \texttt{unsigned-64-bit-aref}.  Return an element at a given
  index of an array of unsigned 64-bit integers.
\item \texttt{(setf unsigned-64-bit-aref)}.  Store an object in the
  element at a given index of an array of unsigned 64-bit integers.
\item \texttt{signed-32-bit-aref}.  Return an element at a given index
  of an array of signed 32-bit integers. 
\item \texttt{(setf signed-32-bit-aref)}.  Store an object in the
  element at a given index of an array of signed 32-bit integers.
\item \texttt{unsigned-32-bit-aref}.  Return an element at a given
  index of an array of unsigned 32-bit integers. 
\item \texttt{(setf unsigned-32-bit-aref)}.  Store an object in the
  element at a given index of an array of unsigned 32-bit integers.
\item \texttt{signed-16-bit-aref}.  Return an element at a given index
  of an array of signed 16-bit integers. 
\item \texttt{(setf signed-16-bit-aref)}.  Store an object in the
  element at a given index of an array of signed 16-bit integers.
\item \texttt{unsigned-16-bit-aref}.  Return an element at a given
  index of an array of unsigned 16-bit integers. 
\item \texttt{(setf unsigned-16-bit-aref)}.  Store an object in the
  element at a given index of an array of unsigned 16-bit integers.
\item \texttt{signed-8-bit-aref}.  Return an element at a given index
  of an array of signed 8-bit integers.
\item \texttt{(setf signed-8-bit-aref)}.  Store an object in the
  element at a given index of an array of signed 8-bit integers.
\item \texttt{unsigned-8-bit-aref}.  Return an element at a given index
  of an array of unsigned 8-bit integers.
\item \texttt{(setf unsigned-8-bit-aref)}.  Store an object in the
  element at a given index of an array of unsigned 8-bit integers.
\item \texttt{single-float-aref}.  Return an element at a given index
  of an array of single floats.
\item \texttt{(setf single-float-aref)}.  Store an object in the
  element at a given index of an array of single floats.
\item \texttt{double-float-aref}.  Return an element at a given index
  of an array of double floats.
\item \texttt{(setf double-float-aref)}.  Store an object in the
  element at a given index of an array of double floats.
\item \texttt{complex-single-float-aref}.  Return an element at a given
  index of an array of single float complex numbers.
\item \texttt{(setf complex-single-float-aref)}.  Store an object in
  the element at a given index of an array of single float complex
  numbers.
\item \texttt{complex-double-float-aref}.  Return an element at a given
  index of an array of double float complex numbers.
\item \texttt{(setf complex-double-float-aref)}.  Store an object in
  the element at a given index of an array of double float complex
  numbers.
\item \texttt{character-aref}.  Return an element at a given index of
  an array of characters.
\item \texttt{(setf character-aref)}.  Store an object in the element
  at a given index of an array of characters.
\item \texttt{bit-aref}.  Return an element at a given index of an
  array of bits.
\item \texttt{(setf bit-aref)}.  Store an object in the element at a
  given index of an array of bits.
\end{itemize}

The following primitives are defined for numbers:

\begin{itemize}
\item \texttt{fixnum-add}.  Add two fixnums the result of which is
  guaranteed to be a fixnum.
\item \texttt{fixnum-subtract}.  Subtract two fixnums the result of
  which is guaranteed to be a fixnum.
\item \texttt{fixnum-multiply}.  Multiply two fixnums, the result of
  which is guaranteed to be a fixnum.
\item \texttt{fixnum-divide}.  Divide two fixnums.  Return the result
  as two values: the quotient and the remainder.  The quotient is
  rounded towards zero.
\item \texttt{fixnum-equal}.  Return true if and only if two fixnums
  are equal.
\item \texttt{fixnum-less}.  Return true if and only if the first
  fixnum is strictly less than the second fixnum.
\item \texttt{fixnum-not-greater}.  Return true if and only if the first
  fixnum is less than or equal to the second fixnum.
\item \texttt{fixnum-logand}.  Return a fixnum that is the bitwise
  logical \emph{and} between two given fixnums.
\item \texttt{fixnum-logior}.  Return a fixnum that is the bitwise
  logical inclusive \emph{or} between two given fixnums.
\item \texttt{fixnum-logxor}.  Return a fixnum that is the bitwise
  logical exclusive \emph{or} between two given fixnums.
\item \texttt{bits-to-single-float}.  Return a single float with the
  same bits in the same order as the non-negative fixnum given as an
  argument.
\item \texttt{bits-to-double-float}.  Return a double float with the
  same bits in the same order as the non-negative integer given as an
  argument.
\item \texttt{single-float-add}.  Return a single float that is the
  sum of two given single-float numbers.
\item \texttt{single-float-subtract}.  Return a single float that is
  the difference of two given single-float numbers.
\item \texttt{single-float-multiply}.  Return a single float that is
  the product of two given single-float numbers.
\item \texttt{single-float-divide}.  Return a single float that is
  the quotient of two given single-float numbers.
\item \texttt{double-float-add}.  Return a double float that is the
  sum of two given double-float numbers.
\item \texttt{double-float-subtract}.  Return a double float that is
  the difference of two given double-float numbers.
\item \texttt{double-float-multiply}.  Return a double float that is
  the product of two given double-float numbers.
\item \texttt{double-float-divide}.  Return a double float that is
  the quotient of two given double-float numbers.
\end{itemize}


\section{Different uses of the compiler}
\label{sec-different-uses-of-the-compiler}

The compiler is used in several different situations.  There are
different use cases, so it is appropriate to distinguish these cases
and identify their respective roles.

\begin{itemize}
\item File compilation.  This use case is relevant when
  \texttt{compile-file} is invoked.  It takes a \commonlisp{} source
  file and generates a so-called \emph{fasl} file.  Since \sysname{}
  \emph{fasl} files are merely textual versions of the abstract syntax
  tree produced by the \iconoclast{} library as described in
  \refChap{chap-compiled-files}, only that phase is involved in file
  compilation.

\item AST compilation.  This use case is relevant when there is an
  existing abstract syntax tree that must be converted into a
  \emph{code object} as described in
  \refSec{data-representation-code-objects}.  The code object is
  initially independent of any particular global environment.  The act
  of associating the code object with any particular environment is
  called \emph{tying} it.  This process, as well as the difference
  between an untied and a tied code object is described in
  \refChap{chap-tying-a-code-object}.

\item \emph{Lambda-expression} compilation.  This use case is relevant
  when \texttt{compile} is called with arguments \texttt{nil} and a
  \emph{lambda expression}, and by \texttt{coerce} to convert a lambda
  expression to a function.  It compiles the lambda expression in the
  \emph{null lexical environment}, and it produces a \emph{function
    object}.  This use case can be seen as the creation of an abstract
  syntax tree from the lambda expression, followed by AST compilation.

\item \emph{Top-level expression} compilation.  This use case is
  relevant when \texttt{eval} is invoked.  It produces a function with
  no parameters which is then immediately \emph{called} by
  \texttt{eval}.  This use case can be thought of as wrapping the
  top-level expression in a lambda expression and then applying
  lambda-expression compilation to it.

\end{itemize}

In addition to these use cases, we also distinguish between different
compilers along an orthogonal dimension:

\begin{itemize}
\item An \emph{intrinsic} (or \emph{native}) compiler is a compiler
  that produces code for its host \commonlisp{} system.
\item An \emph{extrinsic} compiler is a compiler that produces code
  for a \commonlisp{} system other than its host system.  An extrinsic
  compiler is also known as a \emph{cross compiler}.
\end{itemize}

Specific issues related to cross compilation are discussed in
\refChap{chap-cross-compilation}.

\section{Compilation phases}

\subsection{Reading the source code}

\sysname{} uses the \eclector{}%
\footnote{https://github.com/s-expressionists/Eclector}
implementation-independent version of the standard function
\texttt{read} and related functions.

While \eclector{} is also the default reader of \sysname{}, for use
with the compiler, \eclector{} is used to produce a \emph{concrete
  syntax tree}%
\footnote{https://github.com/s-expressionists/Concrete-Syntax-Tree} or
CST for short.  A CST is a direct mirror of the representation of the
source code as ordinary S-expressions, except that each sub-expression
is wrapped in a standard object that may contain other information
\emph{about} the expression.  In particular, the \sysname{} compiler
includes information about \emph{source location} in the CST, so that
this information can be propagated throughout the compilation
procedure.

In order to accomplish source tracking, \sysname{} starts by reading
the entire source file into memory.  The internal representation of
the source code is a vector of lines, where each line is a string.  We
use this representation, rather than a single string for the entire
file, in order to avoid the issue of how newlines are represented.

The macro \texttt{with-source-tracking-stream-from-file} in the
package named \texttt{sicl-source-tracking} takes a file
specification and turns it into a Gray stream by reading the entire
file contents and then wrapping that contents in an instance of the
standard class \texttt{source-tracking-stream}.  An instance of that
class contains the vector of lines of the initial file, the index of the
\emph{current line}, and the index of the \emph{current character}
within the current line.

The library \texttt{trivial-gray-streams} is used to define methods on
the generic functions \texttt{stream-read-char} and
\texttt{stream-unread-char}.  These methods modify the index of the
current line and the current character as appropriate.

The system \texttt{sicl-source-tracking} also defines methods on two
generic functions provided by the \eclector{} subsystem
\texttt{eclector.parse-result}.  The method on
\texttt{source-position} returns an instance of the class
\texttt{sicl-source-position}.  Instances of this class contain the
entire file contents as the vector of lines, together with the line
and character index taken from the current values of the stream.  The
method on \texttt{make-source-range} simply constructs a \texttt{cons}
of the start and the end position, provided they are both non-null.

As a result of this source tracking, every CST that corresponds to a
precise location in the source file has a start and an end position
associated with it.  Not every CST has a location in the source file,
however.  For example, if the source file contains a list in the form
of an opening parenthesis followed by several elements separated by
spaces, then only the CSTs corresponding to the entire list, and those
associated with each element, have source positions associated with
them.  CSTs corresponding to the \texttt{cons} cells of the list,
other than the first, do not have source positions associated with
them.

The source is read in a loop that reads top-level expressions until
end of file.  The expressions are then wrapped in a CST representing
the special operator \texttt{progn} so as to produce a single CST for
the entire source code in the file.

\subsection{Conversion from CST to AST}

Once the CST has been produced by \eclector{}, it is converted to an
\emph{abstract syntax tree}, or AST for short.  We are using the AST
classed defined by the Iconoclast%
\footnote{https://github.com/robert-strandh/Iconoclast}
library.  The conversion itself is done by the Common boot%
\footnote{https://github.com/robert-strandh/Common-boot}
library.  This conversion involves the use of a \emph{global
  environment} as defined in
\refSec{sec-first-class-global-environments} and of lexical
environments that evolve during the compilation procedure, as describe
in \refSec{sec-lexical-compile-time-environments}.

In the AST, all macro calls have been expanded, and all other aspects
of the environment in which the conversion was made have been taken
into account.  For that reason, the AST is independent of any
particular environment.

The AST has a textual representation, so the AST can be saved to a
file and a \emph{similar} AST can be created by an application of the
\texttt{read} function (using a particular read table) to the contents
of the file.  In fact, this textual representation is the \emph{fasl}
format that \sysname{} uses.  It fulfills the requirements for
\emph{minimal compilation} defined by the \commonlisp{} standard.
For more information, see \refChap{chap-compiled-files}.

\subsection{Conversion from AST to HIR}
\label{sec-conversion-from-ast-to-hir}

The acronym HIR stands for \emph{High-level Intermediate
  Representation}.  This representation is defined by the \hirundine{}
library.%
\footnote{https://github.com/robert-strandh/Hirundine}
The main characteristic of HIR is that the objects manipulated are all
\commonlisp{} objects.  This conversion is accomplished by an external
library.

\subsection{HIR transformations}

\subsubsection{Handling \texttt{global-function-reference-instruction}s and similar}

These instructions (together with other instructions that will
ultimately turn into calls to known functions; see below) are scanned
for in the HIR code, and a list of \emph{call-sites} is established.
Otherwise, these instructions are not processed at all.  In the final
native code, they will turn into unconditional jumps, and the target
address will be filled in by the call-site manager when the code is
tied to an environment.

Other instructions are treated the same way.  In particular
\texttt{catch-instruction}s, \texttt{bind-instruction}s,
\texttt{unwind-instruction}s, \texttt{symbol-value-instruction}s, and
\texttt{set-symbol-value-instruction}s.  When these instructions are
scanned for in HIR code, the call sites that are established reflect
the exact kind of instruction.

\subsubsection{Handling non-trivial constants}

Non-trivial constant inputs are handled by the introduction of a
\texttt{load-constant-instruction}.  This instruction has no inputs
and a single lexical output.  The instruction itself contains the
constant.  During later phases, this instruction is replaced by a
PC-relative load instruction that fetches the constant from a vector
of constants allocated separately.

\subsubsection{Eliminating \texttt{create-cell-instruction}s}

A \texttt{create-cell-instruction} is turned into a
\texttt{global-function-reference-instruction} with \texttt{cons} as
the function to call and \texttt{nil} as both the arguments.

Instructions for reading and writing cells are not transformed at the
HIR level, and are instead turned into explicit memory instructions
when HIR is translated to MIR.

\subsection{Conversion from HIR to MIR}

MIR differs from HIR in that address calculations and stack
manipulations are explicit.  MIR operations are defined by the
Posterior library.  In summary, it defines a graph of
\emph{instructions} similar to HIR, but with instructions that are
similar to what most physical processors offer.

We allocate Posterior registers to be used as the stack pointer and
the frame pointer.  Stack operations are then defined in terms of
explicit memory read/write operations involving those registers.

\subsection{Code generation}

Code generation will be handled by the Posterior library, but that
library is still work in progress.

\subsection{Access to special variables and global functions}

To access a special variable, the code must first search the dynamic
environment in case a per-thread binding exists.  If such a binding
exists, a tagged pointer of type \texttt{cons} is returned, but the
pointer refers to an entry on the stack; a dynamic value cell.  If no
such binding exists, the global value cell is returned.

In general, for every access to a special variable, the value cell
must be searched for first.  There are many cases, however, where the
compiler can detect that multiple accesses to some special variable
must refer to the same value cell.  In that case, the (pointer to the)
value cell is a candidate for register allocation, and computing it is
loop invariant.

When it comes to the \emph{contents} of the value cell, however, the
situation is more complicated because of the possibility that multiple
threads might access the (global) value cell concurrently.  In fact,
this is a common situation when a global variable is used for
synchronization purposes.

When some function accesses a special variable multiple times, it
might seem required to read the contents of the value cell for each
such access, even though the compiler can prove that the same cell is
involved in each access.  However, this turns out not to be the case.
If none of the accesses are part of a loop and there is no externally
detectable activity between accesses (no assignment to a global
variable, no function call), then there is always a possible scenario
according to which the same value will be obtained in all the
accesses.  In such cases, not only the value cell, but also the value
itself is a candidate for register allocation.  Even if accesses are
part of a loop, in some cases the value can be cached in a register.
The necessary condition for such register allocation is that the loop
provably \emph{terminates} and that there is no externally detectable
activity between consecutive accesses.

The situation for global functions is similar to that of special
variables, except simpler since no special binding can exist for such
accesses.  While it is not very probable that anyone attempts to use
global functions for synchronization purposes, this can not be
excluded either.  An exception to the rule is when the global function
is a standard \commonlisp{} function, in which case it can not be replaced, so
it is safe to cache the function in a register.

%%  LocalWords:  disjunction
